package lk;


import java.util.ArrayDeque;
import java.util.LinkedList;
import java.util.Queue;


// 最近的请求次数
class RecentCounter {
    Queue<Integer> queue;
    public RecentCounter() {
        queue = new LinkedList<>();
    }

    public int ping(int t) {
        queue.offer(t);
        while (queue.peek() < t - 3000) {
            queue.poll();
        }
        return queue.size();
    }
}


public class D230926 {
    // Dota2 参议院

    // 模拟
    // 时间复杂度：O(n)
    // 空间复杂度：O(n)
    public String predictPartyVictory(String senate) {
        Queue<Character> queue = new ArrayDeque<>();
        int r = 0;  // 表示 r 阵营可以让对方失去权利的数量.
        int d = 0;  // 表示 d 阵营可以让对方失去权利的数量.
        int radiant = 0; // 记录 r 阵营的人数
        int dire = 0;    // 记录 d 阵营的人数

        // 将字符串中的字符, 加入队列, 并且记录双方阵营的人数
        for (char ch : senate.toCharArray()) {
            queue.offer(ch);
            if (ch == 'R') {
                radiant++;
            } else {
                dire++;
            }
        }

        // 模拟投票的过程，直到只剩下一个阵营的人
        while (radiant != 0 && dire != 0) {
            char ch = queue.poll();
            if (ch == 'R' && d > 0) {
                radiant--;
                d--;
            } else if (ch == 'D' && r > 0) {
                dire--;
                r--;
            } else {
                queue.offer(ch);
                if (ch == 'R') {
                    r++;
                } else {
                    d++;
                }
            }
        }
        if (radiant != 0) {
            return "Radiant";
        } else {
            return "Dire";
        }
    }

    // 贪心 + 「循环」队列
    // 时间复杂度：O(n)
    // 空间复杂度：O(n)
    public String predictPartyVictory2(String senate) {
        int n = senate.length();
        Queue<Integer> radiant = new LinkedList<Integer>(); // r 阵营的人
        Queue<Integer> dire = new LinkedList<Integer>();    // d 阵营的人

        // 遍历字符串，将下标存入队列，用于区分出现的顺序
        for (int i = 0; i < n; ++i) {
            if (senate.charAt(i) == 'R') {
                radiant.offer(i);
            } else {
                dire.offer(i);
            }
        }

        // 两个队列各自出来比较，直到一方为空
        while (!radiant.isEmpty() && !dire.isEmpty()) {
            int radiantIndex = radiant.poll(), direIndex = dire.poll();
            // 各出队列一个元素
            // 比较谁先出现，先出现的可以使后出现的失去投票的权利
            // 先出现的可以回到队列，等待下一轮的投票
            if (radiantIndex < direIndex) {
                radiant.offer(radiantIndex + n);
            } else {
                dire.offer(direIndex + n);
            }
        }
        return !radiant.isEmpty() ? "Radiant" : "Dire";
    }
}
